package com.axzh.interview.base;

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		int[] nums = { 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 };
		quickSort(nums, 0, nums.length - 1);
		System.out.println(Arrays.toString(nums));
	}

	public static void quickSort(int[] nums, int left, int right) {
		if (left < right) {
			int p = partition(nums, left, right);
			quickSort(nums, left, p - 1);
			quickSort(nums, p + 1, right);
		}
	}

	public static int partition(int[] nums, int left, int right) {
		int tmp = nums[left];
		while (left < right) {
			while (nums[right] >= tmp && left < right) {
				right--;
			}
			if (left < right) {
				nums[left] = nums[right];
				left++;
			}
			while (nums[left] < tmp && left < right) {
				left++;
			}
			if (left < right) {
				nums[right] = nums[left];
				right--;
			}
		}
		nums[left] = tmp;
		return left;
	}
}
